Keyword based search engines are in widespread use today for information retrieval, such as Web-based information retrieval. Users typically enter queries through a search toolbar. One problem with keyword based search engines and searching on the Web is that it is very common for many irrelevant results to be returned to the user. One reason for this is that the majority of existing search engines utilize a simple “bag of words” approach to search where the user submits one or more query terms and the search engine returns ranked results based on these query terms alone. Better query input by the user results in better ranked results.
Typical existing search engines do not provide a list of query results until the entire query is entered by the user and submitted. As a result, the user has no idea whether their query will provide relevant results until the entire query is entered by the user. Users of typical existing search engines constantly repeat the following cycle: “enter entire query, review results, refine entire query, resubmit entire query.” User time is wasted between these steps, because query results are not available to the user until an entire query is entered and suggested query refinements are not presented to the user. This wasted time degrades the user experience.
Existing systems commonly provide query refinement or query expansion suggestions alongside a traditional ranked list of search results. However, these refinement or expansion suggestions and the ranked list of search results are not provided until after the query has been submitted by the user. For example, a popular topics suggestion may be provided above the search results after the user submits the query. As another example, GOOGLE™ provides “did you mean” suggestions above the search results after the user submits a query.
Many existing search systems with text entry boxes perform some auto-complete function. In UNIX™ and DOS, the command line includes an auto-complete feature. An auto-complete function is included in the INTERNET EXPLERER™ address bar and the OUTLOOK™ address fields. These existing systems typically draw their suggestions only from strings entered by the user in the past or from known entities in the system, such as application, file, or directory names.